#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // vector<vector<int>> threeSum(vector<int> &nums)
    // {
    //     vector<vector<int>> res;
    //     int length = nums.size();
    //     for (int i = 0; i < length - 2; i++)
    //     {
    //         for (int j = i + 1; j < length - 1; j++)
    //         {
    //             for (int k = j + 1; k < length; k++)
    //             {
    //                 if (nums[i] + nums[j] + nums[k] == 0)
    //                 {
    //                     bool flag = true;
    //                     vector<int> vec{nums[i], nums[j], nums[k]};
    //                     sort(vec.begin(), vec.end());
    //                     for (auto vec_check : res)
    //                     {
    //                         if (vec_check == vec)
    //                         {
    //                             flag = false;
    //                         }
    //                     }
    //                     if (flag == true)
    //                     {
    //                         res.push_back(vec);
    //                     }
    //                 }
    //             }
    //         }
    //     }
    //     return res;
    // }

    // vector<vector<int>> threeSum(vector<int> &nums)
    // {
    //     sort(nums.begin(), nums.end());
    //     int length = nums.size();
    //     vector<vector<int>> res;
    //     for (int i = 0; i < length - 2;)
    //     {
    //         int j = i + 1;
    //         int k = length - 1;
    //         while (j < k)
    //         {
    //             if (nums[i] + nums[j] + nums[k] == 0)
    //             {
    //                 res.push_back({nums[i], nums[j], nums[k]});
    //                 j++;
    //                 while (nums[j] == nums[j - 1] && j < length - 1)
    //                 {
    //                     j++;
    //                 }
    //                 k--;
    //                 while (nums[k] == nums[k + 1] && k > 0)
    //                 {
    //                     k--;
    //                 }
    //             }
    //             else if (nums[i] + nums[j] + nums[k] < 0)
    //             {
    //                 j++;
    //                 while (nums[j] == nums[j - 1] && j < length - 1)
    //                 {
    //                     j++;
    //                 }
    //             }
    //             else
    //             {
    //                 k--;
    //                 while (nums[k] == nums[k + 1] && k > 0)
    //                 {
    //                     k--;
    //                 }
    //             }
    //         }
    //         i++;
    //         while (nums[i] == nums[i - 1] && i < length - 1)
    //         {
    //             i++;
    //         }
    //     }
    //     return res;
    // }

    // vector<vector<int>> threeSum(vector<int> &nums)
    // {
    //     sort(nums.begin(), nums.end());
    //     int length = nums.size();
    //     vector<vector<int>> res;
    //     for (int i = 0; i < length; i++)
    //     {
    //         if (nums[0] > 0)
    //         {
    //             return res;
    //         }
    //         if (i > 0 && nums[i] == nums[i - 1])
    //         {
    //             continue;
    //         }
    //         int left=i+1;
    //         int right=length-1;
    //         while(left<right)
    //         {
    //             if(nums[i]+nums[left]+nums[right]<0)
    //             {
    //                 left++;
    //             }
    //             else if(nums[i]+nums[left]+nums[right]>0)
    //             {
    //                 right--;
    //             }
    //             else
    //             {
    //                 res.push_back({nums[i],nums[left],nums[right]});
    //                 while(left<right && nums[left]==nums[left+1])
    //                 {
    //                     left++;
    //                 }
    //                 while(left<right && nums[right]==nums[right-1])
    //                 {
    //                     right--;
    //                 }
    //                 left++;
    //                 right--;
    //             }
    //         }
    //     }
    //     return res;
    // }

    vector<vector<int>> threeSum(vector<int> &nums)
    {
        sort(nums.begin(),nums.end());
        int length=nums.size();
        vector<vector<int>> res;
        for(int i=0;i<length;i++)
        {
            if(nums[0]>0)
            {
                return res;
            }
            if(i>0 && nums[i]==nums[i-1])
            {
                continue;
            }
            unordered_set<int> set;
            for(int j=i+1;j<length;j++)
            {
                if(j>i+2 && nums[j]==nums[j-1] && nums[j-1]==nums[j-2])
                {
                    continue;
                }
                int c=0-nums[i]-nums[j];
                if(set.find(c)!=set.end())
                {
                    res.push_back({nums[i],nums[j],c});
                    set.erase(c);
                }
                else
                {
                    set.insert(nums[j]);
                }
            }
        }
        return res;
    }
};

int main()
{
    vector<int> vec{-1, 0, 1, 2, -1, -4};
    // vector<int> vec{0, 0, 0};
    Solution sol;
    vector<vector<int>> res = sol.threeSum(vec);
    for (auto vec : res)
    {
        for (auto num : vec)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}